{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Word Distance III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestWordDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短单词距离 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串数组&nbsp;<code>wordsDict</code> 和两个字符串 <code>word1</code> 和 <code>word2</code> ，返回这两个单词在列表中出现的最短距离。</p>\n",
    "\n",
    "<p>注意：<code>word1</code> 和 <code>word2</code>&nbsp;是有可能相同的，并且它们将分别表示为列表中 <strong>两个独立的单词</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>wordsDict = [\"practice\", \"makes\", \"perfect\", \"coding\", \"makes\"], word1 = \"makes\", word2 = \"coding\"\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>wordsDict = [\"practice\", \"makes\", \"perfect\", \"coding\", \"makes\"], word1 = \"makes\", word2 = \"makes\"\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= wordsDict.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= wordsDict[i].length &lt;= 10</code></li>\n",
    "\t<li><code>wordsDict[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>word1</code> 和 <code>word2</code> 都在 <code>wordsDict</code> 中</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-word-distance-iii](https://leetcode.cn/problems/shortest-word-distance-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-word-distance-iii](https://leetcode.cn/problems/shortest-word-distance-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"practice\", \"makes\", \"perfect\", \"coding\", \"makes\"]\\n\"makes\"\\n\"coding\"', '[\"practice\", \"makes\", \"perfect\", \"coding\", \"makes\"]\\n\"makes\"\\n\"makes\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import inf\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        pos1: List[int] = [i for i, w in enumerate(words) if w == word1]\n",
    "\n",
    "        if word1 == word2:\n",
    "            return min(pos1[i] - pos1[i - 1] for i in range(1, len(pos1)))\n",
    "\n",
    "        pos2: List[int] = [i for i, w in enumerate(words) if w == word2]\n",
    "\n",
    "        min_dist: int = inf\n",
    "        i: int = 0\n",
    "        j: int = 0\n",
    "\n",
    "        while i < len(pos1) and j < len(pos2):\n",
    "            if pos1[i] < pos2[j]:\n",
    "                min_dist = min(min_dist, pos2[j] - pos1[i])\n",
    "                i += 1\n",
    "            else:  # pos1[i] > pos2[j]\n",
    "                min_dist = min(min_dist, pos1[i] - pos2[j])\n",
    "                j += 1\n",
    "\n",
    "        return min_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        res = inf\n",
    "        idx1 = -1\n",
    "        idx2 = -1\n",
    "        for i in range(len(wordsDict)):\n",
    "            if wordsDict[i] == word1:\n",
    "                idx1 = i\n",
    "                if idx2 != -1:\n",
    "                    res = min(res, abs(idx1 - idx2))\n",
    "            if wordsDict[i] == word2:\n",
    "                idx2 = i\n",
    "                if idx1 != -1 and idx1 != idx2:\n",
    "                    res = min(res, abs(idx1 - idx2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        n = len(wordsDict)\n",
    "        word1_id = []\n",
    "        word2_id = []\n",
    "        ans = n\n",
    "        if word1 != word2:\n",
    "            for i, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    word1_id.append(i)\n",
    "                    if word2_id:\n",
    "                        ans = min(ans, abs(i - word2_id[-1]))\n",
    "                elif word == word2:\n",
    "                    word2_id.append(i)\n",
    "                    if word1_id:\n",
    "                        ans = min(ans, abs(i - word1_id[-1]))\n",
    "            return ans\n",
    "        else:\n",
    "            for i, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    word1_id.append(i)\n",
    "                    if len(word1_id) >= 2:\n",
    "                        ans = min(ans, i-word1_id[-2])\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        res = inf\n",
    "        if word1 == word2:\n",
    "            prev_index = None\n",
    "            for i, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    if prev_index is not None:\n",
    "                        res = min(res, i - prev_index)\n",
    "                    prev_index = i\n",
    "            return res\n",
    "        else:\n",
    "            p1, p2 = -1, -1\n",
    "            for i, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    p1 = i\n",
    "                    if p2 >= 0:\n",
    "                        res = min(res, p1 - p2)\n",
    "                elif word == word2:\n",
    "                    p2 = i\n",
    "                    if p1 >= 0:\n",
    "                        res = min(res, p2 - p1)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        answer = len(wordsDict)\n",
    "        i, j = -1, -1\n",
    "\n",
    "        for k, word in enumerate(wordsDict):\n",
    "            if word == word1 or word == word2:\n",
    "\n",
    "                i = j\n",
    "                j = k\n",
    "\n",
    "            # print(k, i, j)\n",
    "            if i > -1 and j > -1:\n",
    "                if word1 == word2 or wordsDict[i] != wordsDict[j]:\n",
    "                    answer = min(j - i, answer)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        word = [word1,word2]\n",
    "        x = 0\n",
    "        res = inf\n",
    "        save = [inf,inf]\n",
    "        for i,p in enumerate(wordsDict):\n",
    "            if p==word[x%2]:\n",
    "                save[x%2] = i\n",
    "                x+=1\n",
    "                res = min(abs(save[0]-save[1]),res)\n",
    "            elif p==word[(x+1)%2]:\n",
    "                save[(x+1)%2] = i\n",
    "                x+=1\n",
    "                res = min(abs(save[0]-save[1]),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        if word1 == word2:\n",
    "            ans = len(wordsDict)-1\n",
    "            pos = None\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if pos is None:\n",
    "                        pos = i\n",
    "                    else:\n",
    "                        ans = min(ans, i - pos)\n",
    "                        pos = i \n",
    "            return ans\n",
    "        else:\n",
    "            ans = len(wordsDict) - 1\n",
    "            pos1 = None\n",
    "            pos2 = None\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    pos1 = i \n",
    "                elif wordsDict[i] == word2:\n",
    "                    pos2 = i \n",
    "                if pos1 is not None and pos2 is not None:\n",
    "                    ans = min(ans, abs(pos1 - pos2))\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        min_len = 2 ** 31\n",
    "        if word1 != word2:\n",
    "            list_1, list_2 = [], []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    list_1.append(i)\n",
    "                    if list_2:\n",
    "                        min_len = min(min_len, i - list_2[-1])\n",
    "                elif wordsDict[i] == word2:\n",
    "                    list_2.append(i)\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "        else:\n",
    "            list_1 = []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "                    list_1.append(i)\n",
    "        return min_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        min_len = 2 ** 31\n",
    "        if word1 != word2:\n",
    "            list_1, list_2 = [], []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    list_1.append(i)\n",
    "                    if list_2:\n",
    "                        min_len = min(min_len, i - list_2[-1])\n",
    "                elif wordsDict[i] == word2:\n",
    "                    list_2.append(i)\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "        else:\n",
    "            list_1 = []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "                    list_1.append(i)\n",
    "        return min_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        i = 0\n",
    "        while wordsDict[i] != word1 and wordsDict[i] != word2:\n",
    "            i += 1\n",
    "        if wordsDict[i] == word1:\n",
    "            flag = 1\n",
    "        else:\n",
    "            flag = 0\n",
    "        words = [word1,word2]\n",
    "        left = i\n",
    "        right = i+1\n",
    "\n",
    "        ans = len(wordsDict)\n",
    "        while right<len(wordsDict):\n",
    "            if wordsDict[right] == words[flag]:\n",
    "                ans = min(ans,right-left)\n",
    "                left = right\n",
    "                right += 1\n",
    "                flag = 1 - flag\n",
    "            elif wordsDict[right] == words[1-flag]:\n",
    "                left = right\n",
    "                right += 1\n",
    "            else:\n",
    "                right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        res = float(\"inf\")\n",
    "        if word1 == word2:\n",
    "            pre = -1\n",
    "            for i, w in enumerate(wordsDict):\n",
    "                if word1 == w:\n",
    "                    if pre >= 0:\n",
    "                        res = min(res, i-pre)\n",
    "                    pre = i\n",
    "        else:\n",
    "            idx1, idx2 = -1, -1\n",
    "            for i, w in enumerate(wordsDict):\n",
    "                if w == word1:\n",
    "                    idx1 = i\n",
    "                elif w == word2:\n",
    "                    idx2 = i\n",
    "                \n",
    "                if idx1 >= 0 and idx2 >= 0:\n",
    "                    res = min(res, abs(idx1-idx2))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        ans=len(wordsDict)\n",
    "        if word1!=word2:\n",
    "            index1=-1\n",
    "            index2=-1\n",
    "            for i,word in enumerate(wordsDict):\n",
    "                if word==word1:\n",
    "                   index1=i\n",
    "                elif word==word2:\n",
    "                   index2=i \n",
    "                if index1>=0 and index2>=0:\n",
    "                   ans=min(ans,abs(index1-index2))\n",
    "            return ans\n",
    "        j=-1\n",
    "        for i,word in enumerate(wordsDict):\n",
    "            if word==word1:\n",
    "                if j>=0:\n",
    "                    ans=min(ans,i-j)\n",
    "                j=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        i1 = i2 = -1\n",
    "        dist = float('inf')\n",
    "\n",
    "        if word1 == word2:\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if i1 == -1:\n",
    "                        i1 = i\n",
    "                    else:\n",
    "                        i2 = i1\n",
    "                        i1 = i\n",
    "                        dist = min(dist, i1-i2)\n",
    "        else:\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    i1 = i\n",
    "                if wordsDict[i] == word2:\n",
    "                    i2 = i\n",
    "                \n",
    "                if i1>=0 and i2 >=0:\n",
    "                    dist = min(dist, abs(i1-i2))\n",
    "\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        index = -1\n",
    "        ret = inf\n",
    "        if word1 == word2:\n",
    "            for i,word in enumerate(wordsDict):\n",
    "                if word == word2:\n",
    "                    if index == -1:\n",
    "                        index =  i\n",
    "                    else:\n",
    "                        ret = min(ret,i-index)\n",
    "                        index = i\n",
    "        if word2 != word1:\n",
    "            for i,word in enumerate(wordsDict):\n",
    "                if word==word1 or word==word2:\n",
    "                    if index != -1 and word != wordsDict[index]:\n",
    "                        ret = min(ret,i-index)\n",
    "                    index = i\n",
    "        return ret\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: [str], word1: str, word2: str) -> int:\n",
    "        ans = len(wordsDict)\n",
    "        if word1 == word2:\n",
    "            pre = -1\n",
    "            for idx, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    if pre >= 0:\n",
    "                        ans = min(ans, idx - pre)\n",
    "                    pre = idx\n",
    "        else:\n",
    "            index1, index2 = -1, -1\n",
    "            for idx, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    index1 = idx\n",
    "                if word == word2:\n",
    "                    index2 = idx\n",
    "                if (word == word1 or word == word2) and index1 >= 0 and index2 >= 0:\n",
    "                    ans = min(ans, abs(index1 - index2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        index = -1\n",
    "        ret = inf\n",
    "\n",
    "        if word1 == word2:\n",
    "            for i, word in enumerate(wordsDict):\n",
    "                if word == word1:\n",
    "                    if index != -1:\n",
    "                        ret = min(ret, i - index)\n",
    "                    index = i\n",
    "        else:\n",
    "            for i, word in enumerate(wordsDict):\n",
    "                if word == word1 or word == word2:\n",
    "                    if index != -1 and word != wordsDict[index]:\n",
    "                        ret = min(ret, i - index)\n",
    "                    index = i\n",
    "\n",
    "        return ret\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        if word1 == word2:\n",
    "            i1, i2 = 0, 0\n",
    "            while i1 < len(wordsDict) and wordsDict[i1] != word1:\n",
    "                i1 += 1\n",
    "            i2 = i1 + 1\n",
    "            while i2 < len(wordsDict) and wordsDict[i2] != word2:\n",
    "                i2 += 1\n",
    "            ans = 1e9\n",
    "            while i2 < len(wordsDict):\n",
    "                ans = min(ans, i2 - i1)\n",
    "                i1 = i2\n",
    "                i2 += 1\n",
    "                while i2 < len(wordsDict) and wordsDict[i2] != word2:\n",
    "                    i2 += 1\n",
    "            return ans\n",
    "        i1, i2 = 0, 0\n",
    "        while i1 < len(wordsDict) and wordsDict[i1] != word1:\n",
    "            i1 += 1\n",
    "        while i2 < len(wordsDict) and wordsDict[i2] != word2:\n",
    "            i2 += 1\n",
    "        ans = 1e9\n",
    "        while i1 < len(wordsDict) and i2 < len(wordsDict):\n",
    "            ans = min(ans, abs(i1 - i2))\n",
    "            if i1 < i2:\n",
    "                i1 += 1\n",
    "                while i1 < len(wordsDict) and wordsDict[i1] != word1:\n",
    "                    i1 += 1\n",
    "            else:\n",
    "                i2 += 1\n",
    "                while i2 < len(wordsDict) and wordsDict[i2] != word2:\n",
    "                    i2 += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        min_len = 2 ** 31\n",
    "        if word1 != word2:\n",
    "            list_1, list_2 = [], []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    list_1.append(i)\n",
    "                    if list_2:\n",
    "                        min_len = min(min_len, i - list_2[-1])\n",
    "                elif wordsDict[i] == word2:\n",
    "                    list_2.append(i)\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "        else:\n",
    "            list_1 = []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "                    list_1.append(i)\n",
    "        return min_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        min_len = 2 ** 31\n",
    "        if word1 != word2:\n",
    "            list_1, list_2 = [], []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    list_1.append(i)\n",
    "                    if list_2:\n",
    "                        min_len = min(min_len, i - list_2[-1])\n",
    "                elif wordsDict[i] == word2:\n",
    "                    list_2.append(i)\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "        else:\n",
    "            list_1 = []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "                    list_1.append(i)\n",
    "        return min_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        min_len = 2 ** 31\n",
    "        if word1 != word2:\n",
    "            list_1, list_2 = [], []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    list_1.append(i)\n",
    "                    if list_2:\n",
    "                        min_len = min(min_len, i - list_2[-1])\n",
    "                elif wordsDict[i] == word2:\n",
    "                    list_2.append(i)\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "        else:\n",
    "            list_1 = []\n",
    "            for i in range(len(wordsDict)):\n",
    "                if wordsDict[i] == word1:\n",
    "                    if list_1:\n",
    "                        min_len = min(min_len, i - list_1[-1])\n",
    "                    list_1.append(i)\n",
    "        return min_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        word_dict = defaultdict(list)\n",
    "\n",
    "        for idx, w in enumerate(wordsDict):\n",
    "            word_dict[w].append(idx)\n",
    "        \n",
    "        list1 = word_dict[word1]\n",
    "        list2 = word_dict[word2]\n",
    "\n",
    "        p, q = 0, 0\n",
    "        min_dist = float('INF')\n",
    "\n",
    "        while p<len(list1) and q<len(list2):\n",
    "            idx1, idx2 = list1[p], list2[q]\n",
    "            if idx1 < idx2:\n",
    "                min_dist = min(idx2-idx1, min_dist)\n",
    "                p+=1\n",
    "            elif idx1 > idx2:\n",
    "                min_dist = min(idx1-idx2, min_dist)\n",
    "                q+=1\n",
    "            else:\n",
    "                p+=1\n",
    "        \n",
    "        return min_dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        for i, v in enumerate(wordsDict):\n",
    "            d[v].append(i)\n",
    "        mins = float('inf')\n",
    "        if word1 == word2:\n",
    "            l1 = d[word1]\n",
    "            \n",
    "            for i in range(1, len(l1)):\n",
    "                mins = min(abs(l1[i]-l1[i-1]), mins)\n",
    "        else:\n",
    "            l1 = d[word1]\n",
    "            l2 = d[word2]\n",
    "            i1, i2 = 0, 0\n",
    "            while i1 < len(l1):\n",
    "                mins = min(abs(l1[i1]-l2[i2]), mins)\n",
    "                if l1[i1] <= l2[i2]:\n",
    "                    i1 += 1\n",
    "                else:\n",
    "                    i2 += 1\n",
    "                if i2 >= len(l2):\n",
    "                    break\n",
    "        return mins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        data = {}\n",
    "        for i, w in enumerate(wordsDict):\n",
    "            data[w] = data.get(w, []) + [i]\n",
    "        \n",
    "        res = len(wordsDict)\n",
    "        if word1 == word2:\n",
    "            \n",
    "            for i in range(1, len(data[word1])):\n",
    "                res = min(res, data[word1][i] - data[word1][i-1])\n",
    "        else:\n",
    "            i = j = 0 \n",
    "            while i < len(data[word1]) and j < len(data[word2]):\n",
    "                res = min(res, abs(data[word1][i]-data[word2][j]))\n",
    "                if data[word1][i] > data[word2][j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        data = {}\n",
    "        for i, w in enumerate(wordsDict):\n",
    "            data[w] = data.get(w, []) + [i]\n",
    "        \n",
    "        res = len(wordsDict)\n",
    "        if word1 == word2:\n",
    "            \n",
    "            for i in range(1, len(data[word1])):\n",
    "                res = min(res, data[word1][i] - data[word1][i-1])\n",
    "        else:\n",
    "            i = j = 0 \n",
    "            while i < len(data[word1]) and j < len(data[word2]):\n",
    "                res = min(res, abs(data[word1][i]-data[word2][j]))\n",
    "                if data[word1][i] > data[word2][j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i,j in enumerate(wordsDict):\n",
    "            d[j].append(i)\n",
    "        if word2==word1:\n",
    "            return min(d[word1][i+1]-d[word1][i] for i in range(len(d[word1])-1))\n",
    "        if len(d[word2])>len(d[word1]):\n",
    "            word1,word2 = word2,word1\n",
    "        mi = len(wordsDict)\n",
    "        for i in d[word2]:\n",
    "            t = bisect_left(d[word1],i)\n",
    "            if t<len(d[word1]):\n",
    "                mi = min(mi,d[word1][t]-i)\n",
    "            if t>0:\n",
    "                mi = min(mi,i-d[word1][t-1])\n",
    "        return mi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(wordsDict)) : \n",
    "            dic[wordsDict[i]].append(i) \n",
    "        i, j = dic[word1], dic[word2] \n",
    "        p, k = 0, 0\n",
    "        ans = inf \n",
    "        if word1 == word2 : \n",
    "            return min(i[m + 1] - i[m] for m in range(len(i) - 1))\n",
    "        while p < len(i) and k < len(j) : \n",
    "            ans = min(ans, abs(i[p] - j[k]))\n",
    "            if i[p] > j[k] : \n",
    "                k += 1\n",
    "            else : \n",
    "                p += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        hashtable=defaultdict(list)\n",
    "        for i,num in enumerate(wordsDict):\n",
    "            hashtable[num].append(i)\n",
    "        lst1=hashtable[word1]\n",
    "        lst2=hashtable[word2]\n",
    "        i,n=0,len(lst1)\n",
    "        j,m=0,len(lst2)\n",
    "        if word1==word2:\n",
    "            j+=1\n",
    "        ans=inf\n",
    "        while i<n and j<m:\n",
    "            index1=lst1[i]\n",
    "            index2=lst2[j]\n",
    "            if index1-index2!=0:\n",
    "                ans=min(ans,abs(index1-index2))\n",
    "            if index1<index2:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for i, word in enumerate(wordsDict):\n",
    "            dic[word].append(i)\n",
    "        if word1 != word2:\n",
    "            indices1 = dic[word1]\n",
    "            indices2 = dic[word2]\n",
    "            p1 = 0\n",
    "            p2 = 0\n",
    "            res = float(\"inf\")\n",
    "            while p1 < len(indices1) and p2 < len(indices2):\n",
    "                idx1 = indices1[p1]\n",
    "                idx2 = indices2[p2]\n",
    "                res = min(res, abs(idx1 - idx2))\n",
    "                if idx1 < idx2:\n",
    "                    p1 += 1\n",
    "                else:\n",
    "                    p2 += 1\n",
    "            return res\n",
    "        else:\n",
    "            indices = dic[word1]\n",
    "            print(indices)\n",
    "            res = float(\"inf\")\n",
    "            for i in range(1, len(indices)):\n",
    "                res = min(abs(indices[i-1] - indices[i]), res)\n",
    "            return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        w2i = defaultdict(list)\n",
    "        for i, w in enumerate(wordsDict):\n",
    "            w2i[w].append(i)\n",
    "        l1, l2 = w2i[word1], w2i[word2]\n",
    "        if word1 == word2:\n",
    "            return min(i2 - i1 for (i1, i2) in pairwise(l1))\n",
    "        i1, i2 = 0, 0\n",
    "        n1, n2 = len(l1), len(l2)\n",
    "        ans = inf\n",
    "        while i1 < n1 and i2 < n2:\n",
    "            ans = min(ans, abs(l1[i1] - l2[i2]))\n",
    "            if l1[i1] < l2[i2]:\n",
    "                i1 += 1\n",
    "            else:\n",
    "                i2 += 1\n",
    "            # ans = min(ans, abs(l1[i1] - l2[i2]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        data = {}\n",
    "        for i, w in enumerate(wordsDict):\n",
    "            data[w] = data.get(w, []) + [i]\n",
    "        \n",
    "        res = len(wordsDict)\n",
    "        if word1 == word2:\n",
    "            \n",
    "            for i in range(1, len(data[word1])):\n",
    "                res = min(res, data[word1][i] - data[word1][i-1])\n",
    "        else:\n",
    "            i = j = 0 \n",
    "            while i < len(data[word1]) and j < len(data[word2]):\n",
    "                res = min(res, abs(data[word1][i]-data[word2][j]))\n",
    "                if data[word1][i] > data[word2][j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        import bisect\n",
    "        self.wordsDict=wordsDict\n",
    "        self.distance=dict()\n",
    "        count=0\n",
    "        for item in wordsDict:\n",
    "            if self.distance.get(item,-1)==-1:\n",
    "                self.distance[item]=[]\n",
    "            self.distance[item].append(count)\n",
    "            count+=1\n",
    "        for key in self.distance:\n",
    "            self.distance[key]=sorted(self.distance[key])\n",
    "\n",
    "        if word1!=word2:\n",
    "            if len(self.distance[word1])<len(self.distance[word2]):\n",
    "                temp1=self.distance[word1]\n",
    "                temp2=self.distance[word2]\n",
    "            else:\n",
    "                temp1=self.distance[word2]\n",
    "                temp2=self.distance[word1]\n",
    "            temp_dis=100000\n",
    "            for val in temp1:\n",
    "                index=bisect.bisect(temp2,val)\n",
    "                if index!=0:\n",
    "                    temp_dis=min(temp_dis,abs(temp2[index-1]-val))\n",
    "                if index!=len(temp2):\n",
    "                    temp_dis=min(temp_dis,abs(temp2[index]-val))\n",
    "            return temp_dis\n",
    "        else:\n",
    "            temp_dis=100000\n",
    "            last=None\n",
    "            temp1=self.distance[word1]\n",
    "            temp2=self.distance[word2]\n",
    "            for val in temp1:\n",
    "                if last==None:\n",
    "                    last=val\n",
    "                    continue\n",
    "                else:\n",
    "                    temp_dis=min(temp_dis,val-last)\n",
    "                    last=val\n",
    "            return temp_dis\n",
    "\n",
    "\n",
    "# Your WordDistance object will be instantiated and called as such:\n",
    "# obj = WordDistance(wordsDict)\n",
    "# param_1 = obj.shortest(word1,word2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:\n",
    "        import bisect\n",
    "        self.wordsDict=wordsDict\n",
    "        self.distance=dict()\n",
    "        count=0\n",
    "        for item in wordsDict:\n",
    "            if self.distance.get(item,-1)==-1:\n",
    "                self.distance[item]=[]\n",
    "            self.distance[item].append(count)\n",
    "            count+=1\n",
    "        for key in self.distance:\n",
    "            self.distance[key]=sorted(self.distance[key])\n",
    "\n",
    "        if word1!=word2:\n",
    "            if len(self.distance[word1])<len(self.distance[word2]):\n",
    "                temp1=self.distance[word1]\n",
    "                temp2=self.distance[word2]\n",
    "            else:\n",
    "                temp1=self.distance[word2]\n",
    "                temp2=self.distance[word1]\n",
    "            temp_dis=100000\n",
    "            for val in temp1:\n",
    "                index=bisect.bisect(temp2,val)\n",
    "                if index!=0:\n",
    "                    temp_dis=min(temp_dis,abs(temp2[index-1]-val))\n",
    "                if index!=len(temp2):\n",
    "                    temp_dis=min(temp_dis,abs(temp2[index]-val))\n",
    "            return temp_dis\n",
    "        else:\n",
    "            temp_dis=100000\n",
    "            last=None\n",
    "            temp1=self.distance[word1]\n",
    "            temp2=self.distance[word2]\n",
    "            for val in temp1:\n",
    "                if last==None:\n",
    "                    last=val\n",
    "                    continue\n",
    "                else:\n",
    "                    temp_dis=min(temp_dis,val-last)\n",
    "                    last=val\n",
    "            return temp_dis\n",
    "\n",
    "\n",
    "# Your WordDistance object will be instantiated and called as such:\n",
    "# obj = WordDistance(wordsDict)\n",
    "# param_1 = obj.shortest(word1,word2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
